首先预处理出一个人能介绍的人的集合 。(包括他本身)
令 表示让集合 中的人相互认识最少需要几个人。
那么可以刷表转移:
An Ac a day, keeps the doctor away!
因为使用优惠劵就必须买这件商品,我们可以将优惠劵的关系看成一棵树。
令 dp[u][i][0/1] 表示 以 u 为根的子树 , 购买 i 件商品 , u 是否使用优惠劵的最小花费。
边界条件:dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]−d[u]
先考虑所有格子均未涂色的情况。
因为格子的涂色只会影响一行一列,所以可以设 dp(i,j) 表示还需要涂 i 行 , j 列的期望步数。
1.涂色格所在行列均未染色,由 dp(i−1,j−1) 转移,概率为 ni×nj